\documentclass[a4paper, 12pt]{report}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{geometry} 
\usepackage{graphicx}
\usepackage[cc]{titlepic}
\usepackage{hyperref}

%\renewcommand{\labelitemi}{$\bullet$}

\title{Gestion distribu\'ee de l'acc\`es \`a un parking \\ Rapport de projet AD
\\ Master 2}

\titlepic{
\begin{figure}
\centering
\includegraphics[width=200pt,height=150pt]{ufc.jpg}
\end{figure}
}

\author{COUPEY Julien \hspace{15mm} IBRAHIMLI Nihat}
\date{\today}
\begin{document}
\maketitle

\tableofcontents 

\chapter{Introduction}
\paragraph{}
Le but de ce projet est de r\'ealiser la gestion de l'acc\`es \`a un parking. 
Le parking dispose de N places de stationnement et de P portes par lesquelles les voitures peuvent entrer et sortir. 
Le projet simulera la gestion du parking en garantissant qu'aucune voiture ne rentre si elle n'a pas de place pour se garer. 
La bonne gestion des entr\'ees et des sorties sera garantie par un algorithme distribu\'e 
qui r\'ealisera la synchronisation entre les portes (chaque porte ex\'ecute le m\^eme algorithme).
\newpage

\chapter{Pr\'esentation de la structure du projet}
\paragraph{}
Notre projet se d\'ecompose en trois grandes parties \\

\subsubsection{Une biblioth\`eque d'algorithmes}
\begin{itemize}
\item Dans cette partie nous avons implement\'e les fonctions
  \textit{demandeEntree} et \textit{demandeSortie}. L'appel \`a ces fonctions
  permet d'utiliser un algorithme donn\'e de synchronisation qui garantie
  l'acc\`es concurrent aux places de parking.
\item L'algorithme utilisé est défini via un attribut des objets portes.
\end{itemize}
\subsubsection{Les objets portes}
\begin{itemize}
\item D'abord l'objet courant porte re\c{c}oit des demandes d'entr\'ee et de sortie depuis le serveur voiture.
  \item Ensuite il appelle les fonctions \textit{demandeEntree} et \textit{demandeSortie} de l'algorithme associé à l'objet porte.
  \end{itemize}
\subsubsection{Un serveur de voitures}
\begin{itemize}
\item Tout d'abord chacune des portes se déclare aupr\`es du serveur de voiture.
\item On g\'en\`ere ensuite des demandes d'entr\'ee et de sortie de voiture
  al\'eatoirement pour l'ensemble des portes d\'eclar\'ees.
\end{itemize}

\clearpage 
\begin{figure}
%\includegraphics[width=418pt,height=120pt]{struc.jpg}
\includegraphics{structure.png}
\caption{La structure du projet}
\end{figure}
    

 
\chapter{Architecture de communication}
\paragraph{}
La Communication entre le processus est r\'ealis\'ee \`a l'aide de la
technologie RMI (Remote Method Invocation). RMI est un moyen
simple de faire des appels des proc\'edures \`a distance en JAVA.
Pour communiquer, les processus utiliseront un objet distant appel\'e
Reso, le serveur de r\'eseau. De m\^eme, le serveur Reso utilisera des
objets distants (processus \`a distance) afin de passer le message re\c{c}u
depuis un processus \`a un processus cible.
Tout d'abord, repr\'esentons le sch\'ema global 
de la communication entre un processus et le serveur Reso.\\
\begin{figure}[h!] 
\centering
\includegraphics[width=300pt,height=250pt]{rmi.JPG}
\caption{Le principe de RMI}
\end{figure}
 \chapter{D\'eveloppement d'un serveur de voitures}

\section{Principe}

Lors de son lancement, le serveur de voitures effectue successivement les opérations suivantes :
\begin{itemize}
\item déclaration en tant qu'objet distant ;
\item attente de déclaration de toutes les portes ;
\item génération d'un nombre prédéfini de demandes d'entrées ou de sortie. Les dates de demandes sont choisies aléatoirement dans une plage de durée.
\end{itemize}

\section{Garantie apportée}

Le serveur doit garantir que le nombre de demandes de sortie ne dépasse pas le nombre de voitures entrées. En particulier il ne faut pas qu'il génère une demande de sortie lorsque le parking est vide.

Ainsi il est nécessaire de disposer d'un attribut \texttt{nbvoituresentrees} qui compte le nombre de voitures à un instant donné pour que les demandes générées soient cohérentes avec l'état du parking.\\

Voir \ref{ioOK} et \ref{nbvoituresentrees} pour l'implémentation.

\section{Implémentation de la classe \texttt{ServeurVoituresImpl}}

\subsection{Méthode \texttt{attenteDeclaration}}

Comme tous les objets, le serveur connaît le nombre de portes via l'attribut statique \texttt{Porte.nombreportes}. 

Il dispose d'un attribut de type \texttt{ArrayList<Porte> portes}.

\begin{enumerate}
\item Tant que le nombre de portes attendu n'est pas atteint, le serveur utilise \texttt{this.wait()} pour attendre la déclaration suivante.
\item Chaque porte se déclare lors de son lancement via la méthode distante \texttt{ajouterPorte} du serveur.
\item Lorsque toutes les portes sont déclarées, le serveur appelle la méthode \texttt{init} sur chacune des portes.
\end{enumerate}

Le dernier point est nécessaire pour assurer que toutes les portes commencent \og en même temps\fg. C'est indispensable dans le cas de l'algorithme avec jeton pour éviter que la première porte n'essaye de passer le jeton à des portes qui ne sont pas encore déclarées au \texttt{Reso}.

\subsection{Génération des demandes}

La méthode \texttt{envoiDemande} est appelée un nombre de fois égal à l'attribut \texttt{nbdemandes} avec les instructions :\\

\noindent \texttt{delay = (int) (random.nextDouble() * MAX\_DATE\_IN\_SECONDS * 1000);}\\
\texttt{  serveur.envoiDemande(delay, (int) (random.nextDouble()  Porte.nombreportes));}\\

\begin{itemize}
\item L'attribut \texttt{MAX\_DATE\_IN\_SECONDS} permet de choisir la plage temporelle durant laquelle auront lieu les demandes. En effet à chaque appel, \texttt{delay} représente le temps d'attente avant le lancement du thread qui va gérer la demande.
\item Le paramètre \texttt{(int) (random.nextDouble() * Porte.nombreportes)} permet de choisir aléatoirement la porte à laquelle sera adressée la demande.
\end{itemize}

\subsection{Méthode \texttt{envoiDemande}}

Le serveur possède un attribut \texttt{ScheduledThreadPoolExecutor scheduler}. À chaque appel de \texttt{envoiDemande}, on ajoute à cet objet un nouvel objet de type \texttt{Runnable}. L'objet \texttt{scheduler} permet de n'appeler la méthode \textrm{run} du nouvel objet qu'après le délai \texttt{delay}.

\label{ioOK}

Dans la méthode \texttt{run} :
\begin{itemize}
\item si le parking est vide, on doit faire une demande d'entrée ;
\item sinon on choisit au hasard entre entrée et sortie de sorte que la proportion de demandes d'entrées soit proche de l'attribut \texttt{ENTRY\_RATE\_AMONG\_DEMANDS}.			
\end{itemize}

On utilise un booléen \texttt{entree} définit par~:\\

\noindent \texttt{entree = (nbvoituresentrees == 0) ||\newline (random.nextDouble() $<$ ENTRY\_RATE\_AMONG\_DEMANDS);}\\


Le booléen \texttt{random.nextDouble() $<$ ENTRY\_RATE\_AMONG\_DEMANDS} est vrai avec une probabilité de \texttt{ENTRY\_RATE\_AMONG\_DEMANDS}, qui correspondra donc bien à la proportion de demandes d'entrée parmi l'ensemble des demandes (sauf celles effectuées lorsque le parking est vide).

En fonction de la valeur de \texttt{entree}, on appelle la méthode \texttt{demandeEntree} ou \texttt{demandeSortie} sur la porte choisie.

\subsection{Connaissance du nombre de voitures dans le parking}
\label{nbvoituresentrees}

À la fin de l'exécution de la méthode \texttt{demandeEntree} ou \texttt{demandeSortie} de la porte choisie, on sait que le traitement de la demande est effectif. Dans une portion de code synchronisée sur \texttt{nbvoituresentrees}, on incrémente ou on décrémente ce nombre, dans la limite de l'intervalle $[0~;~$\texttt{Porte.nombreplacesinitial}$]$ avec l'une des instructions~:\\

\noindent \texttt{nbvoituresentrees = Math.min(nbvoituresentrees + 1, Porte.nombreplacesinitial);}

\noindent \texttt{nbvoituresentrees = Math.max(nbvoituresentrees - 1, 0);}

				 	
\chapter{La r\'ealisation des objets portes}
Les objets portes assurent les communications entre les différents objets portes
et la transmission à l’algorithme fixé des demandes reçues depuis le serveur de
voiture.
\section{Principe}
Nous avons implémenté les opération suivantes pour la classe
\texttt{PorteImpl}.\\
\begin{itemize}
  \item Deux méthodes pour gérer la communication entre portes~: \texttt{receiveMessage}, \texttt{sendMessage}.  
  \item Méthodes appelées par \texttt{ServeurVoituresImpl}~: \texttt{demandeEntree} et \texttt{demandeSortie}.
  \item  Méthode appelée au démarrage, lorsque toutes les portes sont déclarées~: \texttt{init}.
  \item Création d'une fichier log avec la méthode \texttt{log}
\end{itemize}

\section{Implémentation de la classe \texttt{PorteImpl}}
\subsection{Les operation réalisées lors de la création d'une instance de la
\texttt{PorteImpl}}
Lors de la création de l'instance de la classe \texttt{PorteImpl}, on déclare
cette instance via un objet distant appelé Reso. On fixe le choix de
l'algorithme. Ensuite on ajoute cette instance dans une liste de la classe
distante \texttt{ServeurVoituresImpl} avec sa méthode \texttt{ajouterPorte}.

\subsection{Méthodes \texttt{receiveMessage} et \texttt{sendMessage}}
Les méthodes \texttt{receiveMessage} et \texttt{sendMessage} sont utilisées pour la communication avec le \texttt{Reso}. Respectivement les méthodes \texttt{receiveMessage} et \texttt{sendMessage} de la classe \texttt{PorteImpl}
reçoit un message d'une autre porte (passant par le Reso) et envoie un message à
un autre porte (passant par le Reso). Le traitement des messages est transmis à l'algorithme choisi en appelant sa propre méthode \texttt{receiveMessage}.

\subsection{Méthodes \texttt{demandeEntree} et \texttt{demandeSortie}}
Les méthodes \texttt{demandeEntree} et
\texttt{demandeSortie} sont appelées par le serveur \texttt{ServeurVoituresImpl}.
Les méthodes \texttt{demandeEntree} et \texttt{demandeSortie} nous permettent de
transmettre à l'algorithme fixé repectivement une demande d'entrée et une
demande de sortie d'une voiture appellée par \texttt{ServeurVoitureImpl}.

\subsection{Méthode \texttt{init}}
Dans la méthode on supprime un éventuel fichier de log existant. Ensuite on
appelle la méthode \texttt{init} de l'algorithme de la bibliothèque qui sert à l'initialisation du jeton dans le cas de \texttt{AlgoJeton}.

\subsection{Méthode \texttt{log}}
Dans cette méthode on crée un fichier log dédié à chaque instance de l'objet
\texttt{PorteImpl}.
\chapter{La realisation d'une biblioth\`eque d'algorithmes}

\section{Algorithme de Jeton}

\subsection{Principe et choix d'implémentation}

On a choisi dans la classe \texttt{AlgoJeton} de simuler une structure d'anneau logique à la manière de l'algorithme de section critique de Le Lann, pour la simplicité de son fonctionnement et de son implantation. En outre, ce choix permet d'assurer une équité entre les portes en terme de nombre d'accès et de temps d'attente.\\

Chaque instance dispose comme attribut~:
\begin{itemize}
\item de la référence et de l'\texttt{id} de la \texttt{Porte} qui lui est associée ;
\item de l'id de son \texttt{successeur} : \texttt{(this.id + 1) \% Porte.nombreportes}
\item d'une liste \texttt{threads} qui permet de gérer le traitement des demandes afin qu'aucune ne soit perdue.\\
\end{itemize}

\subsubsection{Rôle des différents objets}

\begin{enumerate}
\item[$\bullet$] Les portes -- en toute rigueur les algorithmes associés à une porte -- étant numérotées dans leur ordre de création, la première envoie un jeton au démarrage lors de l'appel de sa méthode \texttt{init}. Pour la propagation du jeton, chacun l'envoie simplement à son successeur.
\item[$\bullet$] Contrairement au cas d'un algorithme de section critique, le jeton doit posséder une valeur pour transmettre le nombre de places restant disponibles. Les messages seront donc des instances d'une classe \texttt{Jeton} possédant un attribut \texttt{nbplaces}.
\item[$\bullet$] Inutile ici d'utiliser un booléen pour savoir si on est en attente de jeton, il suffit de savoir si des traitements sont en attente par \texttt{!threads.isEmpty()}.
\item[$\bullet$] Lorsqu'un thread de la liste \texttt{threads} est lancé (on possède dans ce cas le jeton), il décide d'accepter ou rejeter une demande d'entrée ou d'enregistrer une demande de sortie. Il transmet ensuite le jeton avec un nombre de places éventuellement modifié.
\item[$\bullet$] On utilise une classe \texttt{GestionThread} qui implémente \texttt{Runnable} pour construire les éléments de la liste \texttt{threads}. La méthode \texttt{run} de cette classe implémente le traitement des demandes d'entrée et de sortie.
\end{enumerate}

\subsection{Synchronisation}

Aucune des méthodes \texttt{demandeEntree}, \texttt{demandeSortie}, \texttt{sendMessage} et \texttt{receiveMessage} n'a besoin d'être synchronisée. Par contre tous les accès à la liste \texttt{threads} le sont~:
\begin{itemize}
\item lorsque l'on reçoit le jeton via \texttt{receiveMessage}, si la liste \texttt{threads} est non vide, on enlève son premier élément et on appelle sa méthode \texttt{start} ;
\item lorsque l'on reçoit une demande d'entrée ou de sortie, on crée un nouveau thread que l'on ajoute à la liste \texttt{threads} (le paramètre booléen du constructeur de \texttt{GestionThread} permet de distinguer une entrée d'une sortie).
\end{itemize}

\subsection{Validation}

La décision d'accorder ou non une entrée ne peut être prise à un instant donné qu'au niveau d'\textbf{une seule} porte, celle qui possède le jeton et qui assurera sa diffusion uniquement après la mise à jour du nombre de places disponibles. 

Ainsi à tout instant la valeur du nombre de places restantes contenue dans le jeton est valide. Comme seule cette valeur fait foi pour toutes les portes, on garantit bien l'accès concurrent aux places de parking, au sens où aucune voiture ne rentrera si elle n'a pas de place pour se garer.


\subsection{Exemple d'exécution}

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 4
[Porte 0] réception de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 3
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 3
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] réception de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 2
[Porte 0] entrée de voiture ACCORDÉE, reste 1 places
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 1
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] réception de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 1
[Porte 0] entrée de voiture ACCORDÉE, reste 0 places
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 0] réception de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 0] réception de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 1
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 1
[Porte 0] réception de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 0] réception de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 0] réception de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
[Porte 0] émission de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
\end{verbatim}

\caption{Traces d'exécution avec \texttt{AlgoJeton}, porte $0$}
\label{jeton0}
\end{figure}

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 4
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 4
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 3
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 3
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 1
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 1
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 1] Demande d'ENTRÉE de voiture
[Porte 1] Demande d'ENTRÉE de voiture
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 1] entrée de voiture REFUSÉE, plus de places !
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 1
[Porte 1] entrée de voiture ACCORDÉE, reste 0 places
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 1] réception de message | from : 0 | to : 1 | Type : JETON | Nombre de places : 0
[Porte 1] émission de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
\end{verbatim}
\caption{Traces d'exécution avec \texttt{AlgoJeton}, porte $1$}
\label{jeton1}
\end{figure}

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 4
[Porte 2] entrée de voiture ACCORDÉE, reste 3 places
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 3
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 3
[Porte 2] entrée de voiture ACCORDÉE, reste 2 places
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 2
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 1
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 1
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] Demande de SORTIE de voiture
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 2] entrée de voiture REFUSÉE, plus de places !
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 2] SORTIE de voiture, reste 1 places
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 1
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 2] entrée de voiture REFUSÉE, plus de places !
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 2] entrée de voiture REFUSÉE, plus de places !
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
[Porte 2] réception de message | from : 1 | to : 2 | Type : JETON | Nombre de places : 0
[Porte 2] émission de message | from : 2 | to : 0 | Type : JETON | Nombre de places : 0
\end{verbatim}

\caption{Traces d'exécution avec \texttt{AlgoJeton}, porte $2$}
\label{jeton2}
\end{figure}
 
Les figures \ref{jeton0},\ref{jeton1} et \ref{jeton2} illustrent le bon fonctionnement de la gestion des entrées (accordées ou refusées) et des sorties lors de l'exécution avec $3$ portes.\\

Paramètres~: \texttt{nombreplacesinitial = 4; nbdemandes = 10;\\ ENTRY\_RATE\_AMONG\_DEMANDS = .8; MAX\_DATE\_IN\_SECONDS = 30;}
 
\section{Algorithme d'horloge logique}
Nous avons étudié trois algorithmes d’horloge logique pour implémenter un
de ces algorithmes dans notre projet. Ces algorithmes sont algorithme de Lamport,  
algorithme de Ricart et Agrawala et Algorithme de Carvalho et Roucairol. 
Pour les raisons suivantes nous avons choisi d’implémenter algorithme de Ricart
et Agrawala comme l’algorithme d’horloge logique \\ 
\begin{enumerate}
   \item Par rapport à l’algorithme de Lamport, Il a une optimisation de
   la complexité 
  \item[] \begin{itemize}
  \item Algorithme de Lamport \textbf{3*(N-1)}
  \item Algorithme de Ricart et Agrawala \textbf{2*(N-1)}
  \item[] d'ou N est le nombre de portes\\ 
\end{itemize}
  \item Dans l’implémentation de l'algorithme de Carvalho et Roucairol,
  lorsqu’un processus sort de section critique, il ne prévient que les processus en attente, par contre l'algorithme de Ricart et Agrawala previent tous les autre processus. On a besoin
	de cette propriété pour informer les autre processus du changement de nombre de
	place dans le parking
\end{enumerate}

\subsection{Principe}
Donc nous avons implementé l‘algorithme de Ricart et Agrawala dans la classe
\texttt{AlgoHorlogeLogique}. Chaque instance de cet objet a des variables
suivantes : \\  
\begin{itemize}
  \item H, un compteur local, initialisé à 0.
   \item HSC, un compteur de demandeur de section critique, initialisé à 0.
   \item R, une variable booléen pour savoir si cet objet est demandeur de
   section critique, initialisé à false.
   \item X, une liste d’entier de demandeur de section critique, initialisé à
   vide.
   \item Nrel, nombre d’accords attendus, initialisé à 0. 
   \item V, une liste d’entier de contenant id des autres portes.
   \item Un objet de message,  contenant deux  instances, une énumération (de
   valaur REQ, REL, SORTIE) et entier.
   \item nbPlace, un compteur de nombre de place.\\
\end{itemize}
Le déroulement de demande d’entrée. On encapsule cette demande dans la méthode
\texttt{demandeEntree}.
\begin{enumerate}
  \item[$\bullet$] Lorsque cette demande arrive sur une instance de cet objet porte,
  tout d’abord on vérifie le nombre de place. Si cette variable est supérieure de zéro
  (il y a de la place disponible) on change la variable de section critique à
  vrai et on envoie un message de type REQ à toutes les portes dont l’identifiant se trouve dans la variable V (à tous voisinage de cet objet).
  \item[$\bullet$] Avant d’entrer en section critique on attend recevoir le
  message de type REL de toutes les autres portes (Nrel est égale à 0).
  \item[$\bullet$]  Apres avoir reçu tous les messages REL on décrémente le
  compteur de place et on change la valeur de section critique à faux. Ensuite on envoie le message de type REL à ceux qui sont attente. 
  On décrémente le compteur de place respectivement pour chaque message de type
  REL.\\
\end{enumerate}  

On implémente de demande de sortie dans la méthode
\texttt{demandeSortie}
	\begin{enumerate}
	  \item[$\bullet$] On incrémente le nombre de place  pour cette instance de
  						l’objet et envoie un message de type SORTIE à tous les autres objets
  						portes.\\
	\end{enumerate}
Tous les messages reçus sur une porte est géré dans la methode
\texttt{receiveMessage}.
\begin{enumerate}
  \item[$\bullet$] Une porte d’identifiant de P1 reçoit un message de type REQ
  (demande d’entrée en section critique) de P0 et on incrémente sa compteur de local(H),
  pour le traitement de cette requête il y a deux cas possible:
  \item[] \begin{itemize}
  			\item[] Cas 1 : si la porte P1 est aussi demandeur de section critique,  et
  			si le compteur de demandeur de section critique de P0 est plus récent que
  			le compteur local de P1, dans ce on enregistre P0 dans la liste de demandeur de section critique.
  			\item[] Cas 2 : sinon on renvoie  un message de type REL en décrémentant
  			l’instance du nombre de place de P1.\\
		\end{itemize}
\item[$\bullet$] Quand on reçoit un message de type REL 
\begin{itemize}
  \item[] on décrémente nombre d’accords attendus(Nrel) et on réveille
  le processus.\\
\end{itemize}
\item[$\bullet$] Quand on reçoit un message de type SORTIE
	\begin{itemize}
	  \item[] on incrémente le nombre de place.\\ 
	\end{itemize}  
\end{enumerate}		  
Envoie le message de type quelconque est implémenté par la méthode
\texttt{sendMessage}.
\subsection{Synchronisation}
	 Chacune de méthodes
	 \texttt{demandeEntree}, \texttt{demandeSortie}, \texttt{sendMessage} et
	 \texttt{receiveMessage}:
\begin{itemize}
  \item Lorsque l'on reçoit une demande d’entrée ou demande de
  sortie, on interdit de recevoir une autre demande sur cet objet jusqu’à l’achèvement de la demande précédente.
\item Lorsque l’on reçoit  un message ou bien on envoie un message on attend
jusqu’à l’achèvement de l’exécution de ces méthodes.
\end{itemize} 

\subsection{Validation}
La décision d’accorder ou non d’une demande d’entrée ne peut être prise en compte à un instant donné que sur une seul porte, celle-ci tient le verrou jusqu’à l’achèvement de cette opération.
Comme à tout l’instant chacune de porte a le nombre de place exacte, on garantit bien qu’aucune voiture ne rentre s’il n’a pas de place pour se garer.

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : REQ | Valeur : 1
[Porte 0] émission de message | from : 0 | to : 2 | Type : REQ | Valeur : 1
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : REQ | Valeur : 1
[Porte 0] émission de message | from : 0 | to : 2 | Type : REQ | Valeur : 1
[Porte 0] réception de message | from : 1 | to : 0 | Type : REL
[Porte 0] réception de message | from : 1 | to : 0 | Type : REQ | Valeur : 3
[Porte 0] émission de message | from : 0 | to : 1 | Type : REL
[Porte 0] réception de message | from : 2 | to : 0 | Type : REL
[Porte 0] entrée de voiture ACCORDEE, reste 3 places
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : REQ | Valeur : 5
[Porte 0] émission de message | from : 0 | to : 2 | Type : REQ | Valeur : 5
[Porte 0] Demande de SORTIE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : SORTIE
[Porte 0] émission de message | from : 0 | to : 2 | Type : SORTIE
[Porte 0] sortie de voiture ACCORDEE, reste 4 places
[Porte 0] réception de message | from : 1 | to : 0 | Type : REL
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : REQ | Valeur : 5
[Porte 0] émission de message | from : 0 | to : 2 | Type : REQ | Valeur : 5
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : REQ | Valeur : 5
[Porte 0] émission de message | from : 0 | to : 2 | Type : REQ | Valeur : 5
[Porte 0] réception de message | from : 2 | to : 0 | Type : REL
[Porte 0] réception de message | from : 1 | to : 0 | Type : REQ | Valeur : 5
[Porte 0] émission de message | from : 0 | to : 1 | Type : REL
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : REQ | Valeur : 7
[Porte 0] émission de message | from : 0 | to : 2 | Type : REQ | Valeur : 7
[Porte 0] réception de message | from : 1 | to : 0 | Type : REL
[Porte 0] réception de message | from : 2 | to : 0 | Type : REL
[Porte 0] entrée de voiture ACCORDEE, reste 2 places
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : REQ | Valeur : 7
[Porte 0] émission de message | from : 0 | to : 2 | Type : REQ | Valeur : 7
[Porte 0] réception de message | from : 1 | to : 0 | Type : REL
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : REQ | Valeur : 7
[Porte 0] émission de message | from : 0 | to : 2 | Type : REQ | Valeur : 7
[Porte 0] Demande de SORTIE de voiture
[Porte 0] émission de message | from : 0 | to : 1 | Type : SORTIE
[Porte 0] émission de message | from : 0 | to : 2 | Type : SORTIE
[Porte 0] sortie de voiture ACCORDEE, reste 3 places
[Porte 0] réception de message | from : 2 | to : 0 | Type : REL
[Porte 0] réception de message | from : 2 | to : 0 | Type : REL
[Porte 0] entrée de voiture ACCORDEE, reste 2 places
[Porte 0] réception de message | from : 2 | to : 0 | Type : REL
[Porte 0] réception de message | from : 1 | to : 0 | Type : REL
[Porte 0] réception de message | from : 2 | to : 0 | Type : REL
[Porte 0] réception de message | from : 1 | to : 0 | Type : REL
[Porte 0] réception de message | from : 1 | to : 0 | Type : REL
[Porte 0] réception de message | from : 1 | to : 0 | Type : SORTIE
[Porte 0] réception de message | from : 1 | to : 0 | Type : REL
[Porte 0] réception de message | from : 2 | to : 0 | Type : REL
\end{verbatim}
\caption{Traces d'exécution avec \texttt{AlgoHorlogeLogique}, porte $0$}
\label{horloge1}
\end{figure}

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 1] réception de message | from : 0 | to : 1 | Type : REQ | Valeur : 1
[Porte 1] émission de message | from : 1 | to : 0 | Type : REL
[Porte 1] Demande d'ENTRÉE de voiture
[Porte 1] émission de message | from : 1 | to : 0 | Type : REQ | Valeur : 3
[Porte 1] émission de message | from : 1 | to : 2 | Type : REQ | Valeur : 3
[Porte 1] réception de message | from : 0 | to : 1 | Type : REQ | Valeur : 1
[Porte 1] émission de message | from : 1 | to : 0 | Type : REL
[Porte 1] Demande d'ENTRÉE de voiture
[Porte 1] émission de message | from : 1 | to : 0 | Type : REQ | Valeur : 5
[Porte 1] émission de message | from : 1 | to : 2 | Type : REQ | Valeur : 5
[Porte 1] réception de message | from : 2 | to : 1 | Type : REL
[Porte 1] réception de message | from : 0 | to : 1 | Type : REL
[Porte 1] entrée de voiture ACCORDEE, reste 2 places
[Porte 1] réception de message | from : 2 | to : 1 | Type : REL
[Porte 1] réception de message | from : 0 | to : 1 | Type : REQ | Valeur : 5
[Porte 1] émission de message | from : 1 | to : 0 | Type : REL
[Porte 1] réception de message | from : 0 | to : 1 | Type : SORTIE
[Porte 1] réception de message | from : 0 | to : 1 | Type : REQ | Valeur : 7
[Porte 1] émission de message | from : 1 | to : 0 | Type : REL
[Porte 1] réception de message | from : 0 | to : 1 | Type : REQ | Valeur : 5
[Porte 1] émission de message | from : 1 | to : 0 | Type : REL
[Porte 1] réception de message | from : 0 | to : 1 | Type : REQ | Valeur : 5
[Porte 1] émission de message | from : 1 | to : 0 | Type : REL
[Porte 1] Demande d'ENTRÉE de voiture
[Porte 1] entrée de voiture REFUSEE, plus de place
[Porte 1] réception de message | from : 0 | to : 1 | Type : REL
[Porte 1] Demande de SORTIE de voiture
[Porte 1] émission de message | from : 1 | to : 0 | Type : SORTIE
[Porte 1] émission de message | from : 1 | to : 2 | Type : SORTIE
[Porte 1] sortie de voiture ACCORDEE, reste 1 places
[Porte 1] réception de message | from : 0 | to : 1 | Type : REQ | Valeur : 7
[Porte 1] émission de message | from : 1 | to : 0 | Type : REL
[Porte 1] réception de message | from : 0 | to : 1 | Type : REQ | Valeur : 7
[Porte 1] émission de message | from : 1 | to : 0 | Type : REL
[Porte 1] Demande d'ENTRÉE de voiture
[Porte 1] entrée de voiture REFUSEE, plus de place
[Porte 1] Demande d'ENTRÉE de voiture
[Porte 1] entrée de voiture REFUSEE, plus de place
[Porte 1] réception de message | from : 0 | to : 1 | Type : SORTIE
\end{verbatim}
\caption{Traces d'exécution avec \texttt{AlgoHorlogeLogique}, porte $1$}
\label{horloge2}
\end{figure}

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 2] réception de message | from : 0 | to : 2 | Type : REQ | Valeur : 1
[Porte 2] émission de message | from : 2 | to : 0 | Type : REL
[Porte 2] réception de message | from : 1 | to : 2 | Type : REQ | Valeur : 3
[Porte 2] émission de message | from : 2 | to : 1 | Type : REL
[Porte 2] réception de message | from : 1 | to : 2 | Type : REQ | Valeur : 5
[Porte 2] émission de message | from : 2 | to : 1 | Type : REL
[Porte 2] réception de message | from : 0 | to : 2 | Type : REQ | Valeur : 1
[Porte 2] émission de message | from : 2 | to : 0 | Type : REL
[Porte 2] réception de message | from : 0 | to : 2 | Type : REQ | Valeur : 5
[Porte 2] émission de message | from : 2 | to : 0 | Type : REL
[Porte 2] réception de message | from : 0 | to : 2 | Type : SORTIE
[Porte 2] réception de message | from : 0 | to : 2 | Type : REQ | Valeur : 5
[Porte 2] émission de message | from : 2 | to : 0 | Type : REL
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] entrée de voiture REFUSEE, plus de place
[Porte 2] réception de message | from : 0 | to : 2 | Type : REQ | Valeur : 5
[Porte 2] émission de message | from : 2 | to : 0 | Type : REL
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] entrée de voiture REFUSEE, plus de place
[Porte 2] réception de message | from : 0 | to : 2 | Type : REQ | Valeur : 7
[Porte 2] émission de message | from : 2 | to : 0 | Type : REL
[Porte 2] réception de message | from : 0 | to : 2 | Type : REQ | Valeur : 7
[Porte 2] émission de message | from : 2 | to : 0 | Type : REL
[Porte 2] réception de message | from : 0 | to : 2 | Type : SORTIE
[Porte 2] réception de message | from : 0 | to : 2 | Type : REQ | Valeur : 7
[Porte 2] émission de message | from : 2 | to : 0 | Type : REL
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] entrée de voiture REFUSEE, plus de place
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] entrée de voiture REFUSEE, plus de place
[Porte 2] réception de message | from : 1 | to : 2 | Type : SORTIE
\end{verbatim}
\caption{Traces d'exécution avec \texttt{AlgoHorlogeLogique}, porte $2$}
\label{horloge3}
\end{figure}

\subsection{Exemple d'exécution}
Les figures \ref{horloge1}, \ref{horloge2} et \ref{horloge3} illustrent le bon fonctionnement de la gestion des entrées (accordées ou refusées) et des sorties de voitures.
Paramètres~: \texttt{nombreportes = 3; nombreplacesinitial = 4; nbdemandes = 20; ENTRY\_RATE\_AMONG\_DEMANDS = .8; MAX\_DATE\_IN\_SECONDS = 10;}	  

\newpage

\section{Algorithme de diffusion}


\subsection{Principe} 

On a choisi dans la classe \texttt{AlgoDiffusion} d'implémenter le protocole \textbf{ABCAST} pour l'échange de messages estampillés.
\begin{enumerate}
\item[$\bullet$] À chaque demande d'entrée ou de sortie, l'algorithme incrémente son estampille. Il envoie ensuite un message contenant son estampille à toutes les autres portes pour indiquer qu'il souhaite traiter la demande.
\item[$\bullet$] Chacune des autres portes répond en indiquant son estampille au moment de la réception puis garde le message en attente (\textit{pending}).
\item[$\bullet$] Quand l'algorithme a reçu tous les accusés de réception estampillés, il choisi l'estampille maximale comme estampille définitive à laquelle le message doit être \og délivré\fg pour lancer le traitement de la demande.
\item[$\bullet$] Il envoie un nouveau message pour diffuser l'estampille définitive à toutes les autres portes qui marquent le message comme prêt à être diffusé (\textit{ready}).
\item[$\bullet$] Sur une porte donnée, un message est diffusé s'il est \textit{ready} et s'il est le premier \textbf{dans l'ordre des estampilles}.\\
\end{enumerate}

Ce protocole nécessite l'échange d'un très grand nombre de messages~: pour déterminer l'estampille définitive et la communiquer à tout le monde, il faut échanger, \textbf{pour chaque demande}, $3N$ messages où $N$ est le nombre de portes.

Cependant, il facilite grandement la gestion de la concurrence~: le traitement de chaque demande est enregistré au niveau de chaque porte lorsqu'un message est délivré. La cohérence d'ensemble est assurée par le fait que \textbf{l'ordre de traitement des demandes est identique} sur toutes les portes, grâce aux estampilles.

\subsection{Choix d'implémentation}

Chaque instance dispose comme attribut~:
\begin{itemize}
\item de la référence et de l'\texttt{id} de la \texttt{Porte} qui lui est associée ;
\item d'un compteur \texttt{nbplaces} indiquant le nombre de places libres ;
\item de sa propre \texttt{estampille} de type \texttt{Estampille} ;
\item d'une liste \texttt{messages} d'objets de type \texttt{Message} (l'ajout de messages dans cette liste est gérée par la méthode statique \texttt{addOrdered} pour assurer que tous les messages y sont rangés \textbf{par ordre croissant d'estampille}).
\item un compteur \texttt{nbAck} permettant de connaître le nombre d'estampilles reçues en réponse.\\
\end{itemize}

\noindent $\bullet$ On utilise une classe \texttt{Estampille} possédant~:
\begin{itemize}
\item une \texttt{date} (qui est incrémentée lors de la réception de message) ;
\item un \texttt{numero} de processus qui permet d'ordonner les estampilles de même date ;
\item une méthode \texttt{estInferieur} qui permet la comparaison d'estampilles (suivant leur \texttt{date}, puis leur \texttt{numero}).\\
\end{itemize}

\noindent $\bullet$ Un objet de type \texttt{Message} possède~:
\begin{itemize}
\item un type (\texttt{ENTREE}, \texttt{SORTIE} ou \texttt{ACK}), élément de la classe d'énumération \texttt{TypMessage} ;
\item l'\texttt{id} de la porte à l'origine de la demande de traitement et un numéro d'ordre (\texttt{numeroordre}) du message sur cette porte\footnote{l'estampille d'un message pending est amenée à être modifiée, par exemple lorsque l'estampille définitive est reçue. D'autre part, la liste \texttt{messages} peut très bien contenir plusieurs messages initiés par le même expéditeur. Pour effectuer une modification d'estampille dans la liste \texttt{messages}, on doit donc pouvoir identifier chaque message (expediteur à l'origine du message ET numero d'ordre).}
\item un booléen \texttt{ready} à \texttt{true} si le message est \textit{ready}, à \texttt{false} s'il est \textit{pending} ;
\item un entier statique \texttt{compte} et une méthode statique \texttt{numero} qui gère atomatiquement l'attribution des numéros d'ordres aux messages à leur création.\\
\end{itemize}

\noindent $\bullet$ La gestion du délivrement des messages est assurée par une classe \texttt{DeliverThread} qui implémente \texttt{Runnable}. Cet objet est lancé à l'initialisation de l'algorithme, il se place en attente. Lorsqu'il est notifié, il lance le traitement du premier message de la liste ordonnée \texttt{messages} si son attribut \texttt{ready} vaut \texttt{true}, le supprime puis recommence tant que le premier message est \textit{ready}.

\subsubsection{Rôle des différentes méthodes}

\begin{enumerate}
\item[$\bullet$] les méthodes \texttt{demandeEntree} et \texttt{demandeSortie} font appel à \texttt{demandeEnvoi} qui implémente ABCAST du point de vue de l'expéditeur d'une demande~:
  \begin{enumerate}
  \item envoi de message de type ENTREE ou SORTIE à toutes les portes ;
  \item récolte des estampilles reçues en retour ;
  \item détermination de l'estampille maximale ;
  \item envoi de l'estampille définitive.
  \end{enumerate}
\item[$\bullet$] la méthode \texttt{receiveMessage} gère les autres aspects~:
  \begin{itemize}
  \item acceptation de message ENTREE ou SORTIE ;
  \item acceptation d'un message ACK estampillé renvoyé à un demandeur ;
  \item acceptation d'un message ESTAMPILLEDEF qui donne l'estampille définitive d'un message.
  \end{itemize}
\end{enumerate}

\subsection{Synchronisation}

\begin{enumerate}
\item[$\bullet$] Les méthodes \texttt{demandeEntree} et \texttt{demandeSortie} qui travaillent sur l'estampille courante sont synchronisées.
\item[$\bullet$] On se synchronise sur l'objet \texttt{DeliverThread}~:
  \begin{itemize}
  \item au début de sa méthode \texttt{run} pour l'attente ;
  \item pour la notification, après la réception d'une estampille définitive qui fait passer un message à \textit{ready}.
  \end{itemize}
\item[$\bullet$] On se synchronise sur la liste \texttt{messages} pour gérer la concurrence~:
  \begin{itemize}
  \item lors du traitement d'un message par \texttt{DeliverThread} ;
  \item lors de la modification de la liste \texttt{messages} après réception d'une estampille définitive.
  \end{itemize}
\item[$\bullet$] On se synchronise sur le compteur \texttt{nbAck}~:
  \begin{itemize}
  \item dans \texttt{demandeEnvoi} pour attendre d'avoir reçu les estampilles de toutes les autres portes ;
  \item pour la notification, lors de l'acceptation d'un message ACK dans \texttt{receiveMessage}.
  \end{itemize}
\end{enumerate}

\subsection{Validation}

Le protocole ABCAST est assez lourd en terme de nombre de messages, cependant une fois mis en place, on est certains que chaque message sera pris en compte avec la même estampille sur chaque porte, donc en particulier \textbf{dans le même ordre}. 

Ainsi toutes les portes peuvent prendre indépendamment les décisions d'accord ou refus concernant toutes les autres portes en incrémentant ou décrémentant leur compteur local \texttt{nbplaces}. On a la certitude que les mêmes décisions seront prises par toutes les portes dans le même ordre, ce qui garantit bien un accès concurrent et cohérent aux places de parking.


\subsection{Exemple d'exécution}

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 0] Demande d'ENTRÉE de voiture
[Porte 0] emission de message | from : 0 | to : 0 | Type : ENTREE | Estampille : 1.0
[Porte 0] emission de message | from : 0 | to : 1 | Type : ENTREE | Estampille : 1.0
[Porte 0] emission de message | from : 0 | to : 2 | Type : ENTREE | Estampille : 1.0
[Porte 0] réception de message | from : 0 | to : 0 | Type : ENTREE | Estampille : 1.0
[Porte 0] emission de message | from : 0 | to : 0 | Type : ACK | Estampille : 2.0
[Porte 0] réception de message | from : 0 | to : 0 | Type : ACK | Estampille : 2.0
[Porte 0] réception de message | from : 2 | to : 0 | Type : ACK | Estampille : 1.2
[Porte 0] réception de message | from : 1 | to : 0 | Type : ENTREE | Estampille : 1.1
[Porte 0] emission de message | from : 0 | to : 1 | Type : ACK | Estampille : 3.0
[Porte 0] réception de message | from : 1 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 3.0
[Porte 0] réception de message | from : 2 | to : 0 | Type : ENTREE | Estampille : 3.2
[Porte 0] emission de message | from : 0 | to : 2 | Type : ACK | Estampille : 4.0
[Porte 0] réception de message | from : 1 | to : 0 | Type : ACK | Estampille : 3.1
[Porte 0] emission de message | from : 0 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 3.1
[Porte 0] emission de message | from : 0 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 3.1
[Porte 0] emission de message | from : 0 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 3.1
[Porte 0] réception de message | from : 2 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 4.2
[Porte 0] réception de message | from : 2 | to : 0 | Type : ENTREE | Estampille : 5.2
[Porte 0] emission de message | from : 0 | to : 2 | Type : ACK | Estampille : 5.0
[Porte 0] réception de message | from : 0 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 3.1
[Porte 0] entrée de voiture ACCORDÉE par la porte 1 avec l'estampille 3.0, reste 1 places
[Porte 0] entrée de voiture ACCORDÉE par la porte 0 avec l'estampille 3.1, reste 0 places
[Porte 0] entrée de voiture REFUSÉE par la porte 2 avec l'estampille 4.2, reste 0 places
[Porte 0] réception de message | from : 2 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 6.2
[Porte 0] entrée de voiture REFUSÉE par la porte 2 avec l'estampille 6.2, reste 0 places
[Porte 0] réception de message | from : 2 | to : 0 | Type : SORTIE | Estampille : 7.2
[Porte 0] emission de message | from : 0 | to : 2 | Type : ACK | Estampille : 6.0
[Porte 0] réception de message | from : 2 | to : 0 | Type : ENTREE | Estampille : 9.2
[Porte 0] emission de message | from : 0 | to : 2 | Type : ACK | Estampille : 7.0
[Porte 0] réception de message | from : 2 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 8.2
[Porte 0] réception de message | from : 2 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 10.2
[Porte 0] SORTIE de voiture à la porte 2 avec l'estampille 8.2, reste 1 places
[Porte 0] entrée de voiture ACCORDÉE par la porte 2 avec l'estampille 10.2, reste 0 places
\end{verbatim}
\caption{Traces d'exécution avec \texttt{AlgoDiffusion}, porte $0$}
\label{diffusion1}
\end{figure}

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 1] Demande d'ENTRÉE de voiture
[Porte 1] emission de message | from : 1 | to : 0 | Type : ENTREE | Estampille : 1.1
[Porte 1] emission de message | from : 1 | to : 1 | Type : ENTREE | Estampille : 1.1
[Porte 1] emission de message | from : 1 | to : 2 | Type : ENTREE | Estampille : 1.1
[Porte 1] réception de message | from : 1 | to : 1 | Type : ENTREE | Estampille : 1.1
[Porte 1] emission de message | from : 1 | to : 1 | Type : ACK | Estampille : 2.1
[Porte 1] réception de message | from : 0 | to : 1 | Type : ENTREE | Estampille : 1.0
[Porte 1] emission de message | from : 1 | to : 0 | Type : ACK | Estampille : 3.1
[Porte 1] réception de message | from : 0 | to : 1 | Type : ACK | Estampille : 3.0
[Porte 1] réception de message | from : 2 | to : 1 | Type : ACK | Estampille : 2.2
[Porte 1] réception de message | from : 2 | to : 1 | Type : ENTREE | Estampille : 3.2
[Porte 1] emission de message | from : 1 | to : 2 | Type : ACK | Estampille : 4.1
[Porte 1] réception de message | from : 1 | to : 1 | Type : ACK | Estampille : 2.1
[Porte 1] emission de message | from : 1 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 3.0
[Porte 1] emission de message | from : 1 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 3.0
[Porte 1] emission de message | from : 1 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 3.0
[Porte 1] réception de message | from : 0 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 3.1
[Porte 1] réception de message | from : 2 | to : 1 | Type : ENTREE | Estampille : 5.2
[Porte 1] emission de message | from : 1 | to : 2 | Type : ACK | Estampille : 5.1
[Porte 1] réception de message | from : 1 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 3.0
[Porte 1] entrée de voiture ACCORDÉE par la porte 1 avec l'estampille 3.0, reste 1 places
[Porte 1] entrée de voiture ACCORDÉE par la porte 0 avec l'estampille 3.1, reste 0 places
[Porte 1] réception de message | from : 2 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 4.2
[Porte 1] entrée de voiture REFUSÉE par la porte 2 avec l'estampille 4.2, reste 0 places
[Porte 1] réception de message | from : 2 | to : 1 | Type : SORTIE | Estampille : 7.2
[Porte 1] emission de message | from : 1 | to : 2 | Type : ACK | Estampille : 6.1
[Porte 1] réception de message | from : 2 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 6.2
[Porte 1] réception de message | from : 2 | to : 1 | Type : ENTREE | Estampille : 9.2
[Porte 1] emission de message | from : 1 | to : 2 | Type : ACK | Estampille : 7.1
[Porte 1] réception de message | from : 2 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 8.2
[Porte 1] entrée de voiture REFUSÉE par la porte 2 avec l'estampille 6.2, reste 0 places
[Porte 1] réception de message | from : 2 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 10.2
[Porte 1] SORTIE de voiture à la porte 2 avec l'estampille 8.2, reste 1 places
[Porte 1] entrée de voiture ACCORDÉE par la porte 2 avec l'estampille 10.2, reste 0 places
\end{verbatim}
\caption{Traces d'exécution avec \texttt{AlgoDiffusion}, porte $1$}
\label{diffusion2}
\end{figure}

\begin{figure}
\scriptsize
\begin{verbatim}
[Porte 2] réception de message | from : 0 | to : 2 | Type : ENTREE | Estampille : 1.0
[Porte 2] emission de message | from : 2 | to : 0 | Type : ACK | Estampille : 1.2
[Porte 2] réception de message | from : 1 | to : 2 | Type : ENTREE | Estampille : 1.1
[Porte 2] emission de message | from : 2 | to : 1 | Type : ACK | Estampille : 2.2
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] emission de message | from : 2 | to : 0 | Type : ENTREE | Estampille : 3.2
[Porte 2] emission de message | from : 2 | to : 1 | Type : ENTREE | Estampille : 3.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ENTREE | Estampille : 3.2
[Porte 2] réception de message | from : 2 | to : 2 | Type : ENTREE | Estampille : 3.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ACK | Estampille : 4.2
[Porte 2] réception de message | from : 1 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 3.0
[Porte 2] réception de message | from : 2 | to : 2 | Type : ACK | Estampille : 4.2
[Porte 2] réception de message | from : 1 | to : 2 | Type : ACK | Estampille : 4.1
[Porte 2] réception de message | from : 0 | to : 2 | Type : ACK | Estampille : 4.0
[Porte 2] emission de message | from : 2 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 4.2
[Porte 2] emission de message | from : 2 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 4.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 4.2
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] emission de message | from : 2 | to : 0 | Type : ENTREE | Estampille : 5.2
[Porte 2] emission de message | from : 2 | to : 1 | Type : ENTREE | Estampille : 5.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ENTREE | Estampille : 5.2
[Porte 2] réception de message | from : 2 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 4.2
[Porte 2] réception de message | from : 2 | to : 2 | Type : ENTREE | Estampille : 5.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ACK | Estampille : 6.2
[Porte 2] réception de message | from : 0 | to : 2 | Type : ACK | Estampille : 5.0
[Porte 2] réception de message | from : 0 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 3.1
[Porte 2] entrée de voiture ACCORDÉE par la porte 1 avec l'estampille 3.0, reste 1 places
[Porte 2] entrée de voiture ACCORDÉE par la porte 0 avec l'estampille 3.1, reste 0 places
[Porte 2] entrée de voiture REFUSÉE par la porte 2 avec l'estampille 4.2, reste 0 places
[Porte 2] réception de message | from : 2 | to : 2 | Type : ACK | Estampille : 6.2
[Porte 2] réception de message | from : 1 | to : 2 | Type : ACK | Estampille : 5.1
[Porte 2] emission de message | from : 2 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 6.2
[Porte 2] emission de message | from : 2 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 6.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 6.2
[Porte 2] Demande de SORTIE de voiture
[Porte 2] emission de message | from : 2 | to : 0 | Type : SORTIE | Estampille : 7.2
[Porte 2] emission de message | from : 2 | to : 1 | Type : SORTIE | Estampille : 7.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : SORTIE | Estampille : 7.2
[Porte 2] réception de message | from : 2 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 6.2
[Porte 2] entrée de voiture REFUSÉE par la porte 2 avec l'estampille 6.2, reste 0 places
[Porte 2] réception de message | from : 2 | to : 2 | Type : SORTIE | Estampille : 7.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ACK | Estampille : 8.2
[Porte 2] réception de message | from : 1 | to : 2 | Type : ACK | Estampille : 6.1
[Porte 2] réception de message | from : 0 | to : 2 | Type : ACK | Estampille : 6.0
[Porte 2] réception de message | from : 2 | to : 2 | Type : ACK | Estampille : 8.2
[Porte 2] emission de message | from : 2 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 8.2
[Porte 2] emission de message | from : 2 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 8.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 8.2
[Porte 2] Demande d'ENTRÉE de voiture
[Porte 2] emission de message | from : 2 | to : 0 | Type : ENTREE | Estampille : 9.2
[Porte 2] emission de message | from : 2 | to : 1 | Type : ENTREE | Estampille : 9.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ENTREE | Estampille : 9.2
[Porte 2] réception de message | from : 2 | to : 2 | Type : ENTREE | Estampille : 9.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ACK | Estampille : 10.2
[Porte 2] réception de message | from : 2 | to : 2 | Type : ACK | Estampille : 10.2
[Porte 2] réception de message | from : 1 | to : 2 | Type : ACK | Estampille : 7.1
[Porte 2] réception de message | from : 2 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 8.2
[Porte 2] SORTIE de voiture à la porte 2 avec l'estampille 8.2, reste 1 places
[Porte 2] réception de message | from : 0 | to : 2 | Type : ACK | Estampille : 7.0
[Porte 2] emission de message | from : 2 | to : 0 | Type : ESTAMPILLEDEF | Estampille : 10.2
[Porte 2] emission de message | from : 2 | to : 1 | Type : ESTAMPILLEDEF | Estampille : 10.2
[Porte 2] emission de message | from : 2 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 10.2
[Porte 2] réception de message | from : 2 | to : 2 | Type : ESTAMPILLEDEF | Estampille : 10.2
[Porte 2] entrée de voiture ACCORDÉE par la porte 2 avec l'estampille 10.2, reste 0 places
\end{verbatim}
\caption{Traces d'exécution avec \texttt{AlgoDiffusion}, porte $2$}
\label{diffusion3}
\end{figure} 

Les figures \ref{diffusion1}, \ref{diffusion2} et \ref{diffusion3} illustrent le bon fonctionnement de la gestion des entrées (accordées ou refusées) et des sorties de voitures. En particulier toutes les décisions concernant toutes les demandes apparaissent \textbf{sur chaque porte} et \textbf{dans le même ordre}.

Paramètres~: \texttt{nombreportes = 3; nombreplacesinitial = 2; nbdemandes = 6; ENTRY\_RATE\_AMONG\_DEMANDS = .8; MAX\_DATE\_IN\_SECONDS = 10;}

\chapter{Conclusion}

% n'hésite pas si tu as des choses à ajouter !

Dans ce projet, nous avons adapté des algorithmes de section critique au cas plus complexe où on doit gérer un nombre donné de places avec des requêtes concurrentes.

Les différentes solutions proposées ont chacune leurs avantages et leurs inconvénients.

\begin{enumerate}
\item[$\bullet$] L'algorithme basé sur un jeton induit des messages inutiles en l'absence de demandes mais assure l'équité pour les portes en terme de nombre d'accès et de temps d'attente.
\item[$\bullet$] L'algorithme de diffusion est très lourd en terme de nombre de messages (et donc en temps). Par contre, en plus d'assurer l'accès concurrent, il permet à \textbf{chaque} porte d'avoir accès à toutes les informations : quelle porte a accordé ou refusé telle ou telle demande et dans quel ordre. Cette connaissance globale au niveau de chaque processus n'est pas obtenue avec les autres algorithmes.
\end{enumerate}

Il est à noter qu'aucun des algorithmes ne gère la tolérance aux pannes ou les problèmes de perte de message.

\end{document}